This application is related to application Ser. No. 08/525,948, filed Sep. 8, 1995 for xe2x80x9cDistributed Processing Systems Having A Host Processor And At Least One Object Oriented Processorxe2x80x9d, now U.S. Pat. No. 5,708,838 issued Jan. 13, 1998 and application Ser. No. 08/683,625, filed Jul. 17, 1996 for xe2x80x9cMethod And Apparatus For Distributed Processing And Rapid ASIC Developmentxe2x80x9d, now U.S. Pat. No. 6,072,944 issued Jun. 6, 2000, the complete disclosures of which are hereby incorporated by reference herein in their entireties.
This application is also related to co-pending applications Ser. No. 09/004,174 filed Jan. 7, 1998 for xe2x80x9cEvent-Reaction Communication Protocol in an Object Oriented Processor Arrayxe2x80x9d, now U.S. Pat. No. 6,052,729 issued Apr. 18, 2000, and Ser. No. 09/003,993 filed Jan, 7, 1998 for xe2x80x9cCentral and Distributed Script Servers in an Object Oriented Processor Arrayxe2x80x9d (IQS-015), both filed simultaneously herewith, and the complete disclosures of which are hereby incorporated by reference herein.
1. Field of the Invention
The invention relates to object oriented processors and processor systems. More particularly, the invention relates to an object oriented processor or processor system which utilizes a library of selectable processor objects in order to implement an array of processor objects. Although not limited thereto, the processors or processor system is preferably arranged such that the processor objects are self-instantiated in virtually any combination, and the processors or processor system is controlled by a high level scripting language.
2. State of the Art
Modern computers permit seemingly simultaneous execution of many operations by interrupting the microprocessor periodically to execute several software threads in turn. For example, as a user types on a keyboard, the input from this peripheral to the microprocessor is seemingly simultaneously displayed by the microprocessor on a video display peripheral. In reality, the microprocessor is interrupted periodically from displaying output on the video display in order to obtain input from the keyboard. It is only because the microprocessor operates at a very high speed that there is an illusion of simultaneity. In a more complex processing system, there may be many threads vying for microprocessor attention at any time. For example, in a desktop multimedia computer, several peripheral devices must be controlled by the microprocessor in a seemingly simultaneous manner in order to produce the proper results and different operations such as displaying video and playing audio must be handled by separate threads. The programming environment in a system having so many threads is incredibly complex. The system software must be written to schedule microprocessor attention to each thread, assign priority to each thread and allow peripherals to interrupt the microprocessor at appropriate times. The system software must then schedule tasks for the microprocessor in response to the interrupts from various peripherals.
In addition to scheduling problems, software in a multi-tasking (multi-threaded) system is difficult to debug. Single stepping techniques cannot be used, since different threads may depend on the results of other threads, and only a single thread can be operational during single stepping.
The handling of interrupts by the microprocessor is determined in part by the bus protocol and in part by the design of the microprocessor itself. Typically, the bus is designed to work with a particular microprocessor or group of microprocessors; and peripheral devices are designed to work with a particular bus. Moreover, each microprocessor-bus system handles interrupts in a different way. This makes it difficult, if not impossible, to adapt program code used on one microprocessor-bus system for use on another.
In order to relieve the host processor from performing every task, multiprocessor systems have been proposed. Some multiprocessor systems are successful in dividing tasks among processors when the tasks are well defined. For example, it is not uncommon to divide tasks between a data processor and a signal processor in systems which deal with signals and data in real time. It is more difficult to divide data processing tasks among several data processors. The operating system must decide which tasks will be performed by which processor and must schedule tasks so that processors do not remain idle while waiting for new tasks or while waiting for other processors to complete tasks so as to provide needed results. Consequently, there has been very little success in developing a general purpose multiprocessor system and there is no standard programming language for programming a multiprocessor system.
U.S. Pat. No. 5,095,522 to Fujita et al. discloses an object-oriented parallel processing system which utilizes xe2x80x9cconcept objectsxe2x80x9d and xe2x80x9cinstance objectsxe2x80x9d. The system utilizes a host processor and a plurality of general purpose processors which are programmed by the host processor. The host user must program (generate concept and instance objects) for each processor before parallel processing can begin. Fujita et al. considers this aspect of their system to be a feature which allows dynamic changes in the functionality of each of the processors. However, this aspect of their system greatly complicates the host processor software.
Similarly, U.S. Pat. No. 5,165,018 to Simor describes a system in which xe2x80x9cnodesxe2x80x9d are provided with generic configuration rules and are configured at runtime via resource definition messages from the control node. Simor considers this aspect of his system to be an advantage which, among other things, xe2x80x9cisolates the hardware from the softwarexe2x80x9d and xe2x80x9callows programs to be written as if they were going to be executed on a single processor.xe2x80x9d In addition, Simor""s system permits programs to be xe2x80x9cdistributed across multiple processors without having been explicitly designed for that purpose.xe2x80x9d
Both Fujita et al. and Simor utilize general purpose processors and attempt to isolate the hardware from the software, freeing the programmer to write code as if it were being executed on a single processor. However, as mentioned above, writing multithreaded software for a single processor is very complex. Neither Fujita et al. nor Simor offer any solution for this complexity.
3. Related Inventions
Related application Ser. No. 08/525,948 approaches the problem of distributed processing in a manner which is completely different from that of either Fujita et al. or Simor. The system disclosed in the ""948 application utilizes processors which have been pre-programmed with functionality for a specific purpose and thereby integrates hardware with software. The developer chooses specific hardware (object oriented processors) in a manner similar to choosing specific software objects. This approach requires that the developer be very aware of the hardware used in the system, but frees the developer from writing much of the code used to implement the system. Accordingly, the developer need only write a minimal amount of relatively high level code to link the pre-programmed object oriented processors which contain statically stored code for performing specific tasks. This approach is based on the belief that writing and de-bugging code is more time consuming and more expensive than linking together processors which contain pre-written, bug-free code. This approach enables rapid system development, relieves the host processor of many scheduling tasks, simplifies de-bugging, enables cross-platform support, allows software emulation of hardware devices, as well as providing other advantages.
According to the ""948 application, object oriented processors communicate with each other and/or with the host processor via the exchange of high level messages. This earliest implementation of the communication protocol required that the host poll at least some of the object oriented processors (i.e. those responsible for processing input data) to determine the availability of data. This was eventually found to detract from the goal of simple coding as the host code had to be written in a manner that would scan all possible input sources on a frequent basis. It was eventually decided that this polling created an undesirable overhead and coding complication. Since many of the originally developed object oriented processors operated in real time, the polling scan rate could be high and thus the overhead could be substantial. In addition, the early communication protocol did not provide information about the source of the data. This was instead derived by specific information requests by the host. Thus, several message exchanges might have been required before both data and source were determined.
Related application Ser. No. 08/683,625 discloses a distributed processing system one or more object oriented processors are embodied as a collection of components on a single ASIC chip. This related application includes an enhanced communication language where the host need not poll the object oriented processors and where messages from one processor to another include source and destination addresses. This communication protocol can be said to be xe2x80x9cevent drivenxe2x80x9d.
In both of the related applications, each object oriented processor has a functionality which defines its physical connectability. More specifically, as embodied on a single chip, each object oriented processor (or collection of object oriented processors) presents a number of pins for coupling the processor to other devices. According to previously disclosed embodiments of the object oriented processors, the functionality of each pin is substantially fixed at the time the object oriented processor is manufactured. For example, as disclosed in related application Ser. No. 08/525,946, a user interface controller ultilizes thirty-seven pins, most of which have a set functionality. Several of the pins have alternate functionality. For example, pins A0 through A7 are an aux port. However, pins A1 and A2 can be used as LCD enable pins and pins A3-A7 can be used as LED enable pins. Nevertheless, for the most part, the functional resources of the object oriented processors are pre-defined with respect to certain pins and cannot be substantially changed by the developer/user.
As used herein, the term xe2x80x9cobject oriented processor arrayxe2x80x9d means a collection of object oriented processors where each object oriented processor incorporates a separate hardware processor, or a collection of object oriented processors where each object oriented processor is embodied as a virtual processor sharing the same hardware processor, or any combination of discrete hardware processors and virtual processors.
It is therefore an object of the invention to provide an object oriented processor array with enhanced post-manufacture configurability.
It is also an object of the invention to provide an object oriented processor array on a chip having a number of pins where the functionality of the pins is configurable by a developer/user.
It is another object of the invention to provide an object oriented processor array which contains a library of functionality which may be selected in virtually any combination.
It is a further object of the invention to provide an object oriented processor array which contains a library of functionality which may be assigned to pins via software commands.
Another object of the invention is to provide an object oriented processor array which utilizes memory in an efficient manner.
In accord with these objects which will be discussed in detail below, an object oriented processor array of the present invention includes a readable memory containing a library of configurable (programmable) functions (also referred to as objects) and a writable memory in which objects are instantiated and configured. More specifically, the object oriented processor array includes a system functionality (system object) which is automatically instantiated in writable memory at power-up, which calls other objects to be instantiated in writable memory in response to commands from a host processor or a boot ROM, and which maintains an active task list and other information about instantiated objects. The object oriented processor array according to the invention further includes a communications interface, an input message processor, and an output message processor. The communications interface allows the object oriented processor array to communicate with other object oriented processor arrays and/or with a host processor. The output message processor preferably includes an external output flow manager for handling messages from processor objects in the array to processor objects external of the array, and a central output registry for queuing messages. According to a presently preferred embodiment, the object oriented processor array is embodied as a virtual machine which is formed from software which runs on a microprocessor. Therefore, the software which embodies the object oriented processor array is provided with a timing kernel which simulates parallelism and a memory manager which allocates memory to objects when they are instantiated.
According to a presently preferred embodiment of the invention, the library of functions is configured as a library of objects stored in ROM. Each object includes a parser layer, a functional layer (which preferably includes a runtime layer and a background layer), a time layer, and an instantiation layer. The system object is also stored in ROM and is automatically instantiated in RAM when the processor array is powered on, and in a preferred embodiment of the invention, reserves RAM for an active task list table (function pointers to instantiated objects), an active task list name table (the names of the instantiated objects), and an active task list data space (pointers to the allocated memory blocks for each instantiated object). The system object is similar to the other objects but handles global methods and functions which are common to all objects and essentially consists of a parser layer only. The most important function of the system object is to call on objects to instantiate themselves.
In response to a high level command from a host processor (or a boot ROM), the system object calls the instantiation layer of an object in the object library and commands the object to instantiate itself in RAM. The instantiation layer of the object calls the memory manager and requests an allocation of RAM. The memory manager returns a pointer (to a starting address in RAM) to the object. According to one embodiment, the object returns the pointer to the system object after performing any necessary initializations to complete instantiation. After the object informs the system object that instantiation was successful, the system object stores a pointer in the active task list table to the portion of the ROM in which the object resides. Each pointer in the active task list is associated with an index number. The system object also stores the name of the instance of the object in the active task list name table which associates the name with the same index number, and stores the pointer to the allocated memory block in the active task list data space which is also associated with the same index number. The system object then recomputes the scheduling of objects in the active task list. According to another embodiment, each instantiated object stores the pointer to its allocated RAM in a reserved area of RAM.
The instantiated object arranges its allocated RAM in several parts. The first part is the output message header which includes a pointer to the output buffer of the object instantiation, the message length, the active task list index, the flow priority of the cell instantiation, the message type, and the source ID. This first part is common in all objects, i.e. every instantiated object has this part in its allocated RAM. The second part is private data used by the cell in the performance of its functionality. This second part may be different for each instantiated object and some objects may arrange additional parts of allocated RAM. Once an object has been thus instantiated, physical pins can be assigned to the instantiation of an object by sending a high level command from a host processor (or boot ROM) to the instantiated object.
The input message processor checks the syntax of all incoming messages, buffers the message, examines the command and looks at the active task list name table to determine the index number for the instantiated object to which the command is directed, and passes the message and the index number to the parser layer of the object. The object parser layer interprets the pin assignment message and stores the pin assignment in its private data area of RAM for the named instantiation of the object.
According to other preferred aspects of the invention, objects may be instantiated several times so long as enough hardware resources (pins and RAM) are available to support another instantiation. The system object keeps track of all object instantiations by placing entries in the active task list table, the active task list name table, and the active task list data space table. In addition, the memory manager maintains a pointer to the memory heap which is utilized and generates an error message if requested to assign more RAM than is available. After pins have been assigned to an instantiation of an object, a message flow priority can be assigned. According to a presently preferred embodiment, a flow priority of 0-7 may be assigned where 0 represents polled priority and 1-7 indicate increasing levels of importance. When the priority level is greater than zero, output messages from the object will be generated autonomously. The flow priority is stored by the instantiation of an object in its output message header part of RAM. During initialization, the system object initiates a global variable or counter indicating the number of active tasks =0. Each time an object is instantiated, this variable is incremented. When the variable is  greater than 0, the system object returns control to the timing kernel which scans the active task list. Each time an object is instantiated, all active tasks are stopped and all instantiated objects are called to their timing layer and the tasks are scheduled. The system object assigns an offset to each object instantiation which the timing layer stores in private data. The object returns a worst case time to the system object and the worst case time is used to calculate the offset for the next active task. The time between the worst case and the actual time is advantageously used by the system object for system (background) functions; i.e. system functions are not otherwise scheduled and therefore do not require overhead.
During operation, a message to a particular instantiation of an object is parsed by the input message processor which scans the active task list name table to find the index to the active task list the pointer to the object instantiation addressed. The object receives the message from the input message processor and the index. The object uses the index and the active task list data space table to find which instantiation of itself is being addressed. Messages from an instantiation of an object are placed in the output message header part of its RAM and a request for registration is sent to the central output registry. The output registry maintains a queue of pointers to messages in output message header parts. The queue is scanned by one or more output flow managers which form output messages from the information held in the output message header parts.
According to other preferred aspects of the invention, a high level language is provided for communication between object oriented processors and a host processor during set-up and during operation. According to a presently preferred embodiment, the high level language messages are exchanged in packets of variable length with a well defined header. The header includes addressing information, an indication of the type of message which follows, an indication of the method or data type, and an indication of the length of the remaining data in the packet. The high level language is self-aligning, simple, and robust.
As mentioned above, the object oriented processor arrays according to the invention are embodied in many alternative constructions including running software on a microprocessor, field programmable gate arrays, multiple microprocessors, and other hardware devices.
Additional objects and advantages of the invention will become apparent to those skilled in the art upon reference to the detailed description taken in conjunction with the provided figures.